package dataStructure.study.search;

import java.util.MissingFormatArgumentException;

/**
 * Author: shangsf
 * Date: 2021/4/15 21:56
 * Description:二分法查找，时间复杂度O(logn)
 * 适合查找有序的数据集合,依赖数组作为数据结构
 */
public class BinarySearch {

    /**
     * 循环迭代,查找指定的值在数组中的索引
     * @param array
     * @param value
     * @return
     */
    public static int search(int[] array, int value){
        if(array==null){
            return -1;
        }
        int low=0;
        int high=array.length-1;

        while (low<=high){
            int mid=low+(high-low)/2;
            if(value==array[mid]){
                return mid;
            }
            if(value<array[mid]){
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }

    /**
     * 递归,指定的值在数组中的索引
     * @param array
     * @param value
     * @return
     */
    public static int search1(int[] array, int value){
        if(array==null){
            return -1;
        }
        return recursion(array,0,array.length-1,value);
    }

    static int recursion(int[] array,int low,int high,int value){
        if(low>high){
            return -1;
        }
        int mid=low+(high-low)/2;
        if(array[mid]==value){
            return mid;
        }else if(value<array[mid]){
            high=mid-1;
            return recursion(array,low,high,value);
        }else {
            low=mid+1;
            return recursion(array,low,high,value);
        }
    }

    /**
     * 查找第一个等于value的数据在数组中的索引
     * @param array
     * @param value
     * @return
     */
    public static int searchFirst(int[] array, int value){
        if(array==null){
            return -1;
        }
        int low=0;
        int high=array.length-1;

        while (low<=high){
            int mid=low+(high-low)/2;
            if(value==array[mid]){
                if(mid-1<0||array[mid-1]<value) {
                    return mid;
                }else {
                    high=mid-1;
                }
            }else if(value<array[mid]){
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }

    /**
     * 查找最后一个等于value的数据在数组中的索引
     * @param array
     * @param value
     * @return
     */
    public static int searchLast(int[] array,int value){
        if(array==null){
            return -1;
        }
        int low=0,n=array.length;
        int high=n-1;

        while (low<=high){
            int mid=low+(high-low)/2;
            if(value==array[mid]){
                if(mid+1==n||array[mid+1]>value) {
                    return mid;
                }else {
                    low=mid+1;
                }
            }else if(value<array[mid]){
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }

    /**
     * 查找值等于value的数据在循环数组中的索引
     * {4,5,6,7,1,2,3}
     * 查找5，result=1
     * 查找2，result=5
     * @param array
     * @param value
     * @return
     */
    public static int searchCircle(int[] array,int value){
        if(array==null){
            return -1;
        }
        int low=0,n=array.length;
        int high=n-1;
        while (low<=high){
            int mid=low+(high-low)/2;
            if(value==array[mid]){
                return mid;
            }else if(value<array[mid]){
                if(value>=array[low]||array[low]>array[mid]){
                    high=mid-1;
                }else {
                    low=mid+1;
                }
            }else {
                if(value<=array[high]||array[mid]>array[high]){
                    low=mid+1;
                }else {
                    high=mid-1;
                }
            }
        }
        return -1;
    }
}
